﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Runtime.Serialization;
using System.Globalization;
using Storage;
using Security;
using Storage.EntityModels;
using Microsoft.SqlServer.Types;

namespace GeoRef
{
    /// <summary>
    /// Represents an entire trip composed of one
    /// or more route, where each one can be done 
    /// with different vehicles
    /// </summary>
    [DataContract]
    [KnownTypeAttribute(typeof(GeoLoc))]
    [KnownTypeAttribute(typeof(GeoPoint))]
    public class GeoTrip
    {
        #region GeoTrip attributes

        /// <value>
        /// Routes list of entire trip
        /// </value>
        [DataMember]
        private List<GeoRoute> routes;

        /// <value>
        /// Identify number of specific trip
        /// </value>
        [DataMember]
        private int id;

        /// <value>
        /// Amount of kilometers covered by entire trip
        /// </value>
        [DataMember]
        private double CoveredDistance;

        /// <value>
        /// Amount of time spent in the trip 
        /// </value>
        [DataMember]
        private int SpentTime;


        /// <value>
        /// Amount of  deviation from the trip
        /// which the owner want to do
        /// </value>
        [DataMember]
        private double deviationRadius;

        #endregion

        #region GeoTrip Constructors

        
        /// <summary>
        /// Parameterless costructor ONLY  for Webservice use
        /// </summary>
        public GeoTrip() 
            : this(new GeoLoc("0, 0", "", ""), new GeoLoc("0.1, 0", "", "")) {
            deviationRadius = -1.0;
        }

        /// <summary>
        /// Initializes a new GeoTrip object, specifying only start and
        /// end points
        /// </summary>
        /// <param name="start">Start point for the trip</param>
        /// <param name="end">End point for the trip</param>
        public GeoTrip(GeoLoc start, GeoLoc end) {
            this.routes = new List<GeoRoute>();
            this.routes.Add(new GeoRoute(start, end));
            this.CoveredDistance = 0.0;
            this.SpentTime = 0;
            deviationRadius = -1.0;
        }

        /// <summary>
        /// Initializes a new GeoTrip object, specifying start point,
        /// end point and a list of intermediate stops
        /// </summary>
        /// <param name="start">Start point for the trip</param>
        /// <param name="end">End point for the trip</param>
        /// <param name="stops">List of intermediate stops</param>
        /// <exception cref="System.ArgumentNullException">If stops is a void list</exception>
        public GeoTrip(GeoLoc start, GeoLoc end, List<GeoLoc> stops) {
            this.routes = new List<GeoRoute>();
            if (stops.Count == 0) {
                throw new System.ArgumentNullException();
            }
            this.routes.Add(new GeoRoute(start, stops.First()));
            for (int i = 0; i < stops.Count - 1; i++) {
                this.routes.Add(new GeoRoute(stops.ElementAt(i), stops.ElementAt(i + 1)));
            }
            this.routes.Add(new GeoRoute(stops.ElementAt(stops.Count - 1), end));
            this.CoveredDistance = 0.0;
            this.SpentTime = 0;
            deviationRadius = -1.0;
        }

        /// <summary>
        /// Initializes a new GeoTrip object using a Storage.EntityModels.Trip
        /// as data source.
        /// </summary>
        /// <param name="dbTrip">The data source</param>
        public GeoTrip(Trip dbTrip) {
            GeoLoc start, stop;
            GeoRoute r;
            this.routes = new List<GeoRoute>();
            List<int> prevUsers = new List<int>();
            List<int> currUsers = new List<int>();

            this.id = dbTrip.Id;
            List<Stage> stages = StorageManager.Instance.GetAllStagesByTripId(dbTrip.Id);
            for (int i = 0; i < stages.Count; i++) {
                Stage s = stages[i];
                currUsers = StorageManager.Instance.GetUserListByStagePk(s.Id);
                currUsers.Sort();
                start = new GeoLoc(s.Origin);
                stop = new GeoLoc(s.Destination);
                if (i > 0) {
                    //sets passengers at current route start
                    start.GettingInUsers.AddRange(currUsers.Except(prevUsers));
                    start.GettingOffUsers.AddRange(prevUsers.Except(currUsers));
                    //sets passengers at previous route end
                    this[i - 1].End.GettingInUsers = start.GettingInUsers;
                    this[i - 1].End.GettingOffUsers = start.GettingOffUsers;
                } else {
                    //sets passengers at current route start 
                    start.GettingInUsers = currUsers;
                }

                r = new GeoRoute(start, stop);
                //r.Id = new KeyValuePair<int,short>(s.TripId, s.Ordinal);
                r.Id = s.Id;
                r.Distance = s.Distance;
                var q = from dinfo in s.DrivingInfos select dinfo;
                foreach (DrivingInfo info in q) {
                    r.Instructions.Add(new GeoLoc((double)info.MapPoint.Lat, (double)info.MapPoint.Long, "", info.Info));
                }
                
                r.Passengers = s.BusySeats;
                r.Time = (s.EstimatedTime == null) ? (short)0 : (short)s.EstimatedTime;
                this.SpentTime += r.Time;

                r.Vehicle = (GeoRef.VehicleType)s.Users_VehicleDetails.VehicleDetails.VehicleClass;
                r.VehicleId = (int)s.Users_VehicleDetails.Id;

                foreach (SqlGeography g in s.GetPath()) {
                    r.PolyLine.Add(new GeoPoint((double)g.Lat, (double)g.Long));
                }

                /*removes first and last point, inserted for storage consistency,
                 * only if vehicle type is car, bycicle or motorbike*/
                if (r.Vehicle < VehicleType.train && r.PolyLine.Count > 3) {
                    r.PolyLine.RemoveAt(0);
                    r.PolyLine.RemoveAt(r.PolyLine.Count - 1);
                }
                foreach (SqlGeography g in s.GetViaPoints()) {
                    r.ViaPoints.Add(new GeoLoc((double)g.Lat, (double)g.Long, "", ""));
                }
                
                this.CoveredDistance += r.Distance;
                
                //consistency: ask to groupware
                this.routes.Add(r);                
                prevUsers = currUsers;
            }
            this[this.Count - 1].End.GettingOffUsers = StorageManager.Instance.GetUserListByStagePk(stages.Last().Id);
            //transform from deviation of db expressed in km to meters
            this.deviationRadius = ((dbTrip.DeviationRadius == null) ? (double) 0.0 : (double) dbTrip.DeviationRadius * 1000);     
        }

        #endregion

        #region GeoTrip Properties

        /// <summary>
        /// Object indexer. Provides a way to access the routes list as an array.
        /// </summary>
        /// <param name="index">The route's index</param>
        /// <returns>The GeoRoute object at the searched position</returns>
        /// <exception cref="System.ArgumentOutOfRangeException">
        /// index is less than 0 or greater than or equal to the number of 
        /// elements in the routes list
        /// </exception>
        /// <example>
        /// <code>
        /// GeoLoc cagliari = new GeoLoc(39.214525, 9.110492, "Cagliari, Italy", "Start point");
        /// GeoLoc olbia = new GeoLoc(40.918045, 9.49601, "Olbia, Italy", "End point");
        /// 
        /// GeoTrip t = new GeoTrip(cagliari, olbia);
        /// 
        /// t[0].InsertViaPoint(new GeoLoc(39.906015, 8.591104, "Oristano, Italy", "a viapoint"));
        /// </code>
        /// </example>
        public GeoRoute this[int index] {
            get { return this.routes.ElementAt(index); }
        }

        /// <summary>
        /// Gets the current routes count
        /// </summary>
        public int Count {
            get { return this.routes.Count; }
        }

        /// <summary>
        /// Gets total covered distance in km
        /// </summary>
        public double TotalDistance {            
            get { return this.CoveredDistance; }
        }

        /// <summary>
        /// Gets total covered distance of route in miles
        /// </summary>
        public double TotalDistanceInMiles {
            get { return this.CoveredDistance / 1.609344; }
        }

        /// <summary>
        /// Gets total spent time in minutes
        /// </summary>
        public int TotalTime {
            get { return this.SpentTime; }
        }

        /// <summary>
        /// Checks for entire trip consistency
        /// </summary>
        /// <returns>True if all routes are consistency, false otherwise</returns>
        public bool IsConsistent {
            get {
                for (int i = 0; i < routes.Count; i++) {
                    if (routes.ElementAt(i).IsConsistent == false) {
                        return false;
                    }
                }
                return true;
            }
        }

        /// <summary>
        /// Returns the starting location for this trip.
        /// </summary>
        public GeoLoc Start
        {
            get {
                if (routes.Count != 0) {
                    return (routes.ElementAt(0).Start);
                }
                return null;
            }
        }

        /// <summary>
        /// Gets and sets trip id
        /// </summary>
        public int Id {
            get { return id; }
            set { id = value; }
        }

        /// <summary>
        /// Returns the location corresponding to the trip's end.
        /// </summary>
        public GeoLoc End {
            get {
                if (routes.Count != 0) {
                    return (routes.ElementAt(routes.Count - 1).End);
                }
                return null;
            }
        }

        /// <summary>
        /// Gets or sets the polyline of entire trip, encoded with
        /// Google Maps API algorithm, as a JSON-serialized
        /// GPolyline object as defined by Google Maps
        /// </summary>
        [DataMember]
        public GPolylineDescriptor[] GPolyline {
            get  {                
                GPolylineBuilder polBuilder = new GPolylineBuilder();
                GPolylineDescriptor[] result = new GPolylineDescriptor[this.routes.Count];                
                int i = 0;
                foreach (GeoRoute r in this.routes) {
                    int[] reduced = polBuilder.DPReduction(r.PolyLine);
                    GPolylineDescriptor json = new GPolylineDescriptor();
                    json.points = polBuilder.Encode(r.PolyLine);
                    json.levels = polBuilder.EncodedLevels;
                    json.zoomFactor = polBuilder.ZoomFactor;
                    json.numLevels = polBuilder.NumLevel;
                    result[i++] = json;
                }
                return result;
            }
            set {
                for (int i = 0; i < value.Count(); i++) {
                    if (this[i].PolyLine == null)
                        this[i].PolyLine = new List<GeoPoint>();
                    else
                        this[i].PolyLine.Clear();
                    this[i].PolyLine.AddRange(GPolylineDecoder.DecodeCoord(value[i].points));
                }
            }
        }

        #endregion

        #region Public GeoTrip Methods        

        /// <summary>
        /// Fills the given dbTrip fields, only geographical informations
        /// </summary>
        /// <param name="dbTrip">Trip object of Storage</param>
        public void FillDbTrip(Trip dbTrip) 
        {
            StorageManager man = StorageManager.Instance;

            /* Lists of Users_Stages used to compute passengers for each Stage,
             * beacause GeoTrip represents passengers as variation between stages,
             * while Storage.Trip keeps a list of passengers associated with each stage */
            List<Users_Stages> gettingInUsersInStage = new List<Users_Stages>();
            List<Users_Stages> gettingOffUsersInStage = new List<Users_Stages>();

            /* In this list we store the ids of the passengers for the current stage,
             * only when the stage we are managing is an old stage (retrived from db).
             * In fact, this happens only in edit mode. */
            List<int> currUsersInStage = new List<int>();

            /* Since that we have to convert the GeoTrip representation of passenger list
             * in "Storage format", for each stage that we are computing we keep in this
             * list the passengers of the previous stage. At iteration i, we compute
             * the passenger list for the i-th stage in this way:
             * PassengerList[i] = (PassengerList[i-1]) U (GettingInPassengers[i]) / (GettingOffPassengers[i])
             * where GettingInPassengers[i] are the passengers that are getting in at the
             * start point of the i-th stage, and GettingOffPassengers[i] are the passengers
             * that are getting off at the same point. This list represents PassengerList[i-1] */
            List<Users_Stages> currUsersInPreviousStage = new List<Users_Stages>();
            
            /* List of id used to store the ids of stages of the old trip version
             * (used only in edit mode) */
            List<int> idRoutes = new List<int>();
            /* Auxiliary variable used in conjunction with the list above */
            int dbPos;

            /* The vehicle class for the stage that we are computing in each
             * iteration of the 'for' block below */
            VehicleType currVehicle = VehicleType.car;

            // By Righetti.
            TripLoaUser ownerTrip = TripLoaUserManager.Instance.getUser(dbTrip.Owner.Username);
            Profile ownerPr = ownerTrip.GetProfile();

            /* If the given dbTrip does not have a real Id then is a new one. We
             * insert it in the db. */
            if (dbTrip.Id == 0) {
                man.Entities.Trips.InsertOnSubmit(dbTrip);
            }

            /* Since this method is used both to insert a new trip and to apply changes
             * to an edited one, in this last case we need to have the old stage list.
             * In this way we can distinguish stages that needs to be modified from
             * new ones */
            List<Storage.EntityModels.Stage> oldStages = dbTrip.Stages.ToList();
            foreach (Stage s in oldStages) {
                idRoutes.Add(s.Id);
            }

            /* We also need to Places that are the Origin and Destination for
             * the i-th stage in the 'for' block above */
            Place stageOrigin, stageDest;

            /* Before start the 'for' cycle that iterates over the route's list
             * we keep note of the first route's start place. At the end of each
             * iteration we'll shift stageOrigin and stageDest. For instance, if
             * we have a trip like this:
             * A----------B------------C
             * in the first iteration we have stageOrigin = A and stageDest = B;
             * at the end of the first iteration we shift origin and destination
             * and we'll have stageOrigin = B and stageDest = C */
            stageOrigin = this.routes[0].Start.SavePlace();
            
            for (int i = 0; i < this.routes.Count; i++) {
                stageDest = this.routes[i].End.SavePlace();
                Stage tmpStage;

                if (this.routes[i].Id <= 0) { //new route, must insert in db
                    tmpStage = new Stage {
                        EstimatedBudget = 0,
                        ReservedSeats = 0
                    };
                    currUsersInPreviousStage = tmpStage.Users_Stages.ToList();
                    if (i > 0) {
                        foreach (Users_Stages passenger in currUsersInPreviousStage) {
                            tmpStage.Users_Stages.Add(new Users_Stages {
                                User = passenger.User,
                                RequestedSeats = 1
                            });
                        }
                    }

                    dbPos = -1;
                } else {   
                    // Existing route, must update.
                    dbPos = idRoutes.BinarySearch(this.routes[i].Id);
                    tmpStage = oldStages[dbPos];
                    currUsersInStage = man.GetUserListByStagePk(tmpStage.Id);
                }
                tmpStage.Ordinal = (short)(i + 1);
                tmpStage.Origin = stageOrigin;
                tmpStage.Destination = stageDest;
                tmpStage.EstimatedTime = this.routes[i].Time;                

                if (this[i].ViaPoints != null && this.routes[i].ViaPoints.Count > 0) {
                    tmpStage.SetViaPoints(this.routes[i].ViaPointsAsMultiPoint);
                } else {
                    this[i].ViaPoints = new List<GeoLoc>();
                }

                // Adds just gotten in passengers.
                foreach (int newPassengerId in this[i].Start.GettingInUsers) {
                    if (!tmpStage.Users_Stages.Any(passenger => passenger.UserId == newPassengerId)) {
                        tmpStage.Users_Stages.Add(new Users_Stages {
                            UserId = newPassengerId
                        });
                    }
                }

                // Removes just gotten off passengers.
                foreach (int oldPassengerId in this[i].Start.GettingOffUsers) {
                    int pos = tmpStage.Users_Stages.ToList().FindIndex(delegate(Users_Stages u) { return (u.UserId == oldPassengerId); });
                    if (pos >= 0) {
                        tmpStage.Users_Stages.RemoveAt(pos);
                    }
                }

                
                tmpStage.Users_VehicleDetails =
                    ownerPr.UsersVehiclesDetails.First(d => d.Id == routes[i].VehicleId);

                currVehicle = (VehicleType)tmpStage.Users_VehicleDetails.VehicleDetails.VehicleClass;

                if (currVehicle >= VehicleType.train) {
                    this[i].Update();
                } else { //for road vehicles
                    //sets owner as driver 
                    tmpStage.DriverId = dbTrip.OwnerId;
                }

                if (currVehicle == VehicleType.train) {
                    tmpStage.SetPath(this.routes[i].PolylineAsLineString, true);
                } else {
                    tmpStage.SetPath(this.routes[i].PolyLineAsMultiPoint, false);
                }

                if (tmpStage.Id <= 0) {
                    dbTrip.AddStage(tmpStage);
                } else {
                    if (dbPos >= 0) {
                        idRoutes.Remove(tmpStage.Id);
                        oldStages.RemoveAt(dbPos);
                    }
                }
                
                stageOrigin = stageDest;
            }

            // Stages that are still in oldStages must be removed.
            if (oldStages.Count > 0) {
                man.Entities.Stages.DeleteAllOnSubmit(oldStages);
                foreach (Stage toDelete in oldStages) {
                    dbTrip.Stages.Remove(toDelete);
                }
            }
        }

        /// <summary>
        /// Inserts a new stop splitting the route identified by index
        /// </summary>
        /// <param name="stop">The new stop to insert</param>
        /// <param name="index">The index of the route to split</param>
        /// <remarks> Route of the given index mantains all viaPoints,
        /// even if this is splitted by stop location</remarks>
        /// <exception cref="System.ArgumentOutOfRangeException">If the given index is outside routes list range</exception>
        public void InsertStop(GeoLoc stop, int index) {            
            GeoRoute newR1;
            if (index < 0 || index >= this.routes.Count) {
                throw new System.ArgumentOutOfRangeException();
            }
            GeoLoc oldStart = this.routes.ElementAt(index).Start;
            GeoLoc oldEnd = this.routes.ElementAt(index).End;
            this.routes[index].End = stop;
            newR1 = new GeoRoute(stop, oldEnd);            
            newR1.Vehicle = this.routes[index].Vehicle;
            newR1.VehicleId = this.routes[index].VehicleId;
            this.routes.Insert(index + 1, newR1);            
        }

        /// <summary>
        /// Substitutes an existing route identified by index with a pair of consecutive routes
        /// </summary>
        /// <param name="splitRoute1">The first new route</param>
        /// <param name="splitRoute2">The second new route</param>
        /// <param name="index">The index of the route to substitute</param>
        /// <exception cref="System.ArgumentException">If the start point of splitRoute1 does not
        /// match the start point of the old route
        /// or
        /// If the end point of splitRoute1 does not match the start point of splitRoute2
        /// or
        /// If the end point of splitRoute2 does not match the end point of the old route</exception>
        public void ReplaceRoute(GeoRoute splitRoute1, GeoRoute splitRoute2, int index) {            
            if (splitRoute1.Start != this.routes.ElementAt(index).Start ||
                splitRoute1.End != splitRoute2.Start ||
                splitRoute2.End != this.routes.ElementAt(index).End) {
                throw new System.ArgumentException();
            }
            this.CoveredDistance -= this[index].Distance;
            this.SpentTime -= this[index].Time;
            this.routes.RemoveAt(index);

            this.routes.Insert(index, splitRoute1);
            this.routes.Insert(index + 1, splitRoute2);
            this.CoveredDistance += (splitRoute1.Distance + splitRoute2.Distance);
            this.SpentTime += (splitRoute1.Time + splitRoute2.Time);
        }

        /// <summary>
        /// Removes a specific stop, merging two consecutive routes
        /// </summary>
        /// <param name="stop">Intermediate stop to remove</param>
        public void RemoveStop(GeoLoc stop) {
            int index = -1;
            if (this.IsConsistent == true) {
                if (stop == routes.ElementAt(routes.Count - 1).End) {
                    this.SpentTime -= routes.ElementAt(routes.Count - 1).Time;
                    this.CoveredDistance -= routes.ElementAt(routes.Count - 1).Distance;
                    routes.Remove(routes.ElementAt(routes.Count - 1));                    
                } else if (stop == routes.ElementAt(0).Start) {
                    this.CoveredDistance -= routes.ElementAt(0).Distance;
                    this.SpentTime -= routes.ElementAt(0).Time;
                    routes.Remove(routes.ElementAt(0));
                } else {
                    index = routes.FindIndex(delegate(GeoRoute r) { return (r.End == stop); });
                    if (index >= 0) {
                        routes[index].End = routes[index + 1].End;
                        routes[index].ViaPoints.AddRange(routes[index + 1].ViaPoints);
                        routes[index].Instructions.AddRange(routes[index + 1].Instructions);
                        routes[index].PolyLine.AddRange(routes[index + 1].PolyLine);
                        routes.RemoveAt(index + 1);
                    }
                }
            }
        }

        /// <summary>
        /// Merges the route at firstIndex position with the route at firstIndex + 1, if it exists
        /// </summary>
        /// <param name="firstIndex">The index of the first route of the pair to merge</param>
        public void MergeRoutes(int firstIndex) {
            if (this.Count >= 2 && firstIndex >= 1 && firstIndex <= this.Count - 2) {
                RemoveStop(this[firstIndex].End);
            }
        }
        
        /// <summary>
        /// Updates all inconsistent routes
        /// </summary>
        public void UpdatePath(){
            this.CoveredDistance = 0;
            this.SpentTime = 0;
            foreach (GeoRoute r in routes){
               if (r.IsConsistent == false) {
                   r.Update();
               }
               this.CoveredDistance += r.Distance;
               this.SpentTime += r.Time;
            }
        }

        /// <summary>
        /// Sets the vehicle type used for the route at index "route"
        /// </summary>
        /// <param name="vehicle">The vehicle type</param>
        /// <param name="route">The route index</param>
        /// <exception cref="System.ArgumentOutOfRangeException">
        /// If route is less than zero or greater than or equal to the
        /// number of routes in the list
        /// </exception>
        public void SetVehicle(VehicleType vehicle, int route) {
            this.routes[route].Vehicle = vehicle;
        }

        /// <summary>
        /// Appends a new route at the end of
        /// route list
        /// </summary>
        /// <param name="newR">new route to insert</param>
        /// <exception cref="ArgumentException">If end of old last route
        /// differs from start of new last route</exception>
        public void AddRoute(GeoRoute newR) {
            if (this.routes.Last().End != newR.Start) {
                throw new ArgumentException();
            } else {
                this.routes.Add(newR);
                this.CoveredDistance += newR.Distance;
                this.SpentTime += newR.Time;
            }
        }

        /// <summary>
        /// Checks consistency for entire trip
        /// </summary>
        /// <returns>True if all routes are consistent,
        /// false otherwise</returns>
        public bool CheckTotalConsistency() {
            bool check = true;
            foreach (GeoRoute r in this.routes) {
                check &= r.CheckConsistency();
            }
            return check;
        }

        /// <summary>
        /// Gets the index of the route where the given user is getting in
        /// </summary>
        /// <param name="userId">The user Id to search</param>
        /// <returns>
        /// The route's index if the user is found in a route, -1 otherwise
        /// </returns>
        public int GetInRoute(int userId) {
            for (int i = 0; i < this.Count; i++) {
                if (this[i].Start.GettingInUsers.Contains(userId)) {
                    return i;
                }
            }
            return -1;
        }

        /// <summary>
        /// Gets the index of the route where the given user is getting off
        /// </summary>
        /// <param name="userId">The user Id to search</param>
        /// <returns>
        /// The route's index if the user is found in a route, -1 otherwise
        /// </returns>
        public int GetOffRoute(int userId) {
            for (int i = this.Count - 1; i >= 0; i--) {
                if (this[i].End.GettingOffUsers.Contains(userId)) {
                    return i;
                }
            }
            return -1;
        }

        /// <summary>
        /// Gets the <see cref="GeoLoc"/> where the given user is getting in
        /// </summary>
        /// <param name="userId">The user Id to search</param>
        /// <returns>
        /// The <see cref="GeoLoc"/> where the user gets in if found, null otherwise
        /// </returns>
        public GeoLoc GetInPlace(int userId) {
            int i = GetInRoute(userId);
            if (i >= 0) {
                return this[i].Start;
            }
            return null;
        }

        /// <summary>
        /// Gets the <see cref="GeoLoc"/> where the given user is getting off
        /// </summary>
        /// <param name="userId">The user Id to search</param>
        /// <returns>
        /// The <see cref="GeoLoc"/> where the user gets off if found, null otherwise
        /// </returns>
        public GeoLoc GetOffPlace(int userId) {
            int i = GetOffRoute(userId);
            if (i >= 0) {
                return this[i].End;
            }
            return null;
        }

        /// <summary>
        /// Retrieves the id of routes modified after the
        /// addition of the given user to the trip.
        /// </summary>
        /// <param name="userId">The user to search</param>
        /// <returns>
        /// Returns a pair of id of route if the user is a passenger 
        /// of the trip, otherwise a single value equal to -1.
        /// </returns>
        public List<int> GetModifiedRouteByPassenger(int userId) {
            List<int> result = new List<int>();
            int gettingInIndex = GetInRoute(userId);
            int gettingOffIndex = -1;
            if (gettingInIndex == -1) {
                result.Add(-1);
                return result;
            } else {
                gettingOffIndex = GetOffRoute(userId);
                //passenger getting in and off in the same route
                if (gettingOffIndex == gettingInIndex) {
                    //the route is not the first
                    if (gettingInIndex > 0) {
                        result.Add(this[gettingInIndex - 1].Id);
                        result.Add(this[gettingInIndex - 1].Id);
                    } else {
                        result.Add(this[gettingInIndex].Id);
                        result.Add(this[gettingInIndex].Id);
                    }
                } else {
                    /*new route caused by the addition of a new stop
                      for the getting in passenger*/
                    if (this[gettingInIndex].Id == -1) {
                        result.Add(this[gettingInIndex - 1].Id);
                    } else {
                        result.Add(this[gettingInIndex].Id);
                    }
                    /*the current route for the getting off stop of
                      the passenger*/
                    result.Add(this[gettingOffIndex].Id);
                }
            }
            return result;
        }

        /// <summary>
        /// Gets the list of the fellow passengers for the given user id
        /// </summary>
        /// <param name="userId">The user Id to search</param>
        /// <returns>
        /// A list of user id that can be empty. If the given user is not
        /// among the trip's passengers list it returns null
        /// </returns>
        public List<int> GetUserFellowPassengers(int userId) {
            List<int> result = new List<int>();
            int getInIndex = GetInRoute(userId);
            if (getInIndex == -1) {
                return null;
            }
            int getOffIndex = GetOffRoute(userId);

            for (int i = 0; i < getInIndex; i++) {
                result.AddRange(this[i].Start.GettingInUsers);
                result.Except(this[i].End.GettingOffUsers);
            }

            for (int i = getInIndex; i <= getOffIndex; i++) {
                result.AddRange(this[i].Start.GettingInUsers);
            }

            result.RemoveAll(delegate(int user) { return (user == userId); });
            return result.Distinct().ToList();
        }

        #endregion

        #region Protected Internal GeoTrip Method

        /// <summary>
        /// Forces an update of all trip routes
        /// </summary>
        protected internal void ForceUpdate() {
            this.CoveredDistance = 0;
            this.SpentTime = 0;
            foreach (GeoRoute r in routes) {
                r.Update();
                this.CoveredDistance += r.Distance;
                this.SpentTime += r.Time;
            }
        }
        #endregion        

        #region Private GeoTrip.GPolylineBuilder class

        /// <summary>
        /// Class used to transform a polyline described
        /// as List&lt;<see cref="GeoPoint" />&gt; into a  
        /// <seealso href="http://code.google.com/apis/maps/documentation/reference.html#GPolyline">
        /// GPolyline</seealso> point list using the
        /// <seealso href="http://code.google.com/apis/maps/documentation/polylinealgorithm.html">
        /// Google polyline encoding algorithm</seealso>
        /// </summary>
        internal class GPolylineBuilder
        {
            /// <summary>
            /// A representation of a segment as pair of indexes
            /// </summary>
            private struct Segment
            {
                /// <value>
                /// Beginning index for the segment
                /// </value>
                private int first;

                /// <value>
                /// Finishing index for the segment
                /// </value>
                private int last;

                /// <summary>
                /// Creates a new segment from the given start
                /// index to the given finished index
                /// </summary>
                /// <param name="f">Start index</param>
                /// <param name="l">Stop index</param>
                public Segment(int f, int l) {
                    this.first = f;
                    this.last = l;
                }

                /// <summary>
                /// Sets or gets the first index of segment
                /// </summary>
                public int First {
                    get { return this.first; }
                    set { this.first = value; }
                }

                /// <summary>
                /// Sets or gets the last index of segment
                /// </summary>
                public int Last {
                    get { return this.last; }
                    set { this.last = value; }
                }
            };

            #region GeoTrip.GPolylineBuilder fields

            /// <value>
            /// Number of levels of a G_NORMAL_MAP defined
            /// by <seealso href="http://code.google.com/apis/maps/documentation/reference.html">
            /// Google Maps API</seealso> 
            /// </value>
            static int MAP_LEVELS = 18;

            /// <value>
            /// Absolute value of the exponent for the minimum
            /// precision tolerance value
            /// </value>
            static Double MIN_PRECISION_TOLERANCE_EXP = 1.0;


            /// <value>
            /// Absolute value of the exponent for the maximum
            /// precision tolerance value
            /// </value>
            static Double MAX_PRECISION_TOLERANCE_EXP = 5.0;

            /// <value>
            /// The number of zoom levels contained in the
            /// encoded levels string.
            /// </value>
            private int numL = 1;

            /// <value>
            /// String of encoded level for points
            /// </value>
            StringBuilder resLevels;

            /// <value>
            /// The magnification between adjacent sets of
            /// zoom levels in the encoded levels  string.
            /// </value>
            private int zoomF;

            /// <value>
            /// Array of tolerance values used by line reduction
            /// algorithm to compute the visualization level
            /// for each line point
            /// </value>
            private Double[] tolerances;

            #endregion

            #region GeoTrip.GPolylineBuilder constructors

            /// <summary>
            /// Initializes a new GPolyline object 
            /// with a default number of levels and
            /// a default zoom factor
            /// </summary>
            public GPolylineBuilder() {
                this.tolerances = new Double[4];
                this.NumLevel = 4;
                resLevels = new StringBuilder();
            }

            /// <summary>
            /// Initializes a new GPolyline object 
            /// with a specified number of levels and
            /// consequently computed zoom factor
            /// </summary>
            /// <param name="numLevel">Specified number of levels</param>
            public GPolylineBuilder(int numLevel) {
                this.tolerances = new Double[numLevel];
                this.NumLevel = numLevel;
                resLevels = new StringBuilder();
            }

            #endregion

            #region GeoTrip.GPolylineBuilder methods

            /// <summary>
            /// Takes a list of coordinates in decimal value and
            /// multiply it by 1e5, flooring the result.
            /// </summary>
            /// <param name="pol">The list of coordinates to 
            /// encode</param>
            /// <returns>The polyline as an encoded string</returns>
            internal string Encode(List<GeoPoint> pol) {
                int prevLat = 0;
                int prevLng = 0;
                StringBuilder resPoints = new StringBuilder();
                resLevels.Remove(0, resLevels.Length);

                //takes the visualization level for each point according to DP-reduction
                int[] pointLevels = DPReduction(pol);
                for (int i = 0; i < pol.Count; i++) {
                    //DP-reduction returns level -1 for those points that can be ignored
                    //without loss of detail, so we can ignore those points
                    if (pointLevels[i] == -1) {
                        continue;
                    }
                    //rounds coordinates of polyline points
                    int convLat = (int)(pol[i].Lat * 1e5);
                    int convLng = (int)(pol[i].Lng * 1e5);
                    //calculates difference between current point and previous point
                    resPoints.Append(EncodeSignedNumber(convLat - prevLat));
                    resPoints.Append(EncodeSignedNumber(convLng - prevLng));
                    //Compute the visualization level according with DP-reduction result
                    resLevels.Append(EncodeNumber(pointLevels[i]));
                    prevLat = convLat;
                    prevLng = convLng;
                }
                return resPoints.ToString();
            }

            /// <summary>
            /// Encodes a signed number according specified
            /// format
            /// </summary>
            /// <param name="n">signed number</param>
            /// <returns>Output string of encoding</returns>
            private static string EncodeSignedNumber(int n) {
                //shift binary
                int sgn_n = n << 1;
                //invetes negative number
                if (n < 0) {
                    sgn_n = ~(sgn_n);
                }

                return (EncodeNumber(sgn_n)); 
            }

            /// <summary>
            /// Encodes an unsigned number according specified
            /// format
            /// </summary>
            /// <param name="num">unsigned number</param>
            /// <returns>Output string of encoding</returns>
            private static string EncodeNumber(int num) {
                StringBuilder encodeString = new StringBuilder();
                //checks every 5-block of digit
                while (num >= 0x20) {
                    //OR each value with 0x20 and add it 63
                    int nextValue = (0x20 | (num & 0x1f)) + 63;
                    encodeString.Append((char)(nextValue));
                    num >>= 5;
                }

                num += 63;
                encodeString.Append((char)(num));

                return encodeString.ToString();
            }

            /// <summary>
            /// Computes a visualization level for each point of
            /// the list given as input, using an adapted version of
            /// the Douglas-Peucker line semplification algorithm.
            /// </summary>
            /// <param name="points">The polyline as a points list</param>
            /// <returns>
            /// An array of integer representing the visualization
            /// level for each input point. The level is a value between
            /// -1 (the point can be ignored) and numLevel - 1 (the point
            /// must be visible at every zoom level)
            /// </returns>
            internal int[] DPReduction (List<GeoPoint> points) {
                if (points == null || points.Count < 3) {
                    int[] ret = new int[points.Count];
                    for (int i = 0; i < ret.Length; i++) {
                        ret[i] = this.NumLevel - 1;
                    }
                    return ret;
                }

                int firstPoint = 0;
                int lastPoint = points.Count - 1;

                int[] indexesToKeep = new int[points.Count];
                double[] distances = new double[points.Count];
                
                Stack<Segment> stack = new Stack<Segment>();
                Segment current;
                Double maxDistance = 0;
                int indexMostDistant = 0;

                //this will throw an exception if all points are equals!
                while (points[firstPoint] == points[lastPoint]) {
                    lastPoint--;
                }

                indexesToKeep[firstPoint] = this.NumLevel - 1;
                indexesToKeep[lastPoint] = this.NumLevel - 1;

                stack.Push(new Segment(firstPoint, lastPoint));

                while (stack.Count > 0) {
                    current = stack.Pop();
                    maxDistance = 0;
                    indexMostDistant = -1;

                    for (int i = current.First+1; i < current.Last; i++) {
                        Double distance = PerpDistance(points[current.First], points[current.Last], points[i]);
                        if (distance > maxDistance) {
                            maxDistance = distance;
                            indexMostDistant = i;
                        }
                    }
                    //if maxDistance is less than the minimum threshold value, 
                    //all the segment's points (excluding bounds) can be
                    //aproximated by a straight line, so it sets the level
                    //to -1 for each intermediate point and skips the
                    //current iteraction
                    if (maxDistance < this.tolerances[0]) {
                        for (int i = current.First + 1; i < current.Last; i++) {
                            indexesToKeep[i] = -1;
                        }
                        continue;
                    }

                    indexesToKeep[indexMostDistant] = -1;
                    for (int i = 0; i < this.tolerances.Length; i++) {
                        if (maxDistance > this.tolerances[i] && indexMostDistant != 0) {
                            distances[indexMostDistant] = maxDistance;
                            indexesToKeep[indexMostDistant] = i;
                        }
                    }
                    if (indexMostDistant < current.Last - 1) {
                        stack.Push(new Segment(indexMostDistant, current.Last));
                    }
                    if (indexMostDistant > current.First + 1) {
                        stack.Push(new Segment(current.First, indexMostDistant));
                    }

                }

                return indexesToKeep;
            }

            /// <summary>
            /// Computes the distance between the point x and the segment
            /// with bounds p1 and p2
            /// </summary>
            /// <param name="p1">First point of the segment</param>
            /// <param name="p2">Last point of the segment</param>
            /// <param name="x">Point of which compute the distance from the segment</param>
            /// <returns>The distance between the point and the segment</returns>
            internal static Double PerpDistance(GeoPoint p1, GeoPoint p2, GeoPoint x) {
                Double up = Math.Abs((x.Lng - p1.Lng) * (p2.Lat - p1.Lat) - (x.Lat - p1.Lat) * (p2.Lng - p1.Lng));
                Double down = Math.Sqrt(Math.Pow((p2.Lng - p1.Lng), 2) + Math.Pow((p2.Lat - p1.Lat), 2));
                return (up / down);
            }
            #endregion

            #region GeoTrip.GPolylineBuilder properties

            /// <summary>
            /// Sets and gets number of levels
            /// </summary>
            internal int NumLevel {
                set {
                    if (this.numL < 1 || this.numL > MAP_LEVELS) {
                        throw new ArgumentOutOfRangeException();
                    } else if (value != this.numL) {
                        this.numL = value;
                        int factor = MAP_LEVELS / this.numL;
                        int mod = MAP_LEVELS % this.numL;
                        this.zoomF = 2 << ((mod > (this.numL >> 1)) ? (factor + 1) : factor);

                        Double increment = (MAX_PRECISION_TOLERANCE_EXP - MIN_PRECISION_TOLERANCE_EXP) / (this.numL - 1);
                        this.tolerances = new Double[this.numL];
                        this.tolerances[0] = Math.Pow(10, -MAX_PRECISION_TOLERANCE_EXP);
                        for (int i = 1; i < this.tolerances.Length - 1; i++) {
                            this.tolerances[i] = Math.Pow(10, -(MAX_PRECISION_TOLERANCE_EXP - (increment * i)));
                        }
                        this.tolerances[this.tolerances.Length - 1] = Math.Pow(10, -MIN_PRECISION_TOLERANCE_EXP);
                    }
                }
                get { return this.numL; }
            }

            /// <summary>
            /// Gets zoomFactor
            /// </summary>
            internal int ZoomFactor {                
                get { return this.zoomF; }
            }

            /// <summary>
            /// Gets a string which describes encoded
            /// level for each point of polyline
            /// </summary>
            internal string EncodedLevels {
                get { return resLevels.ToString(); }
            }

            #endregion

        }
        
        #endregion

        #region GPolylineDecoder

        /// <summary>
        /// Groups two static methods used to decode a GPolyline line
        /// and convert it into a List&lt;GeoPoint&gt;
        /// </summary>
        internal class GPolylineDecoder {

            /// <summary>
            /// Decodes a polyline in GPolyline format and returns it
            /// as a List&lt;<see cref="GeoPoint"/>&gt;
            /// </summary>
            /// <param name="encoded">The string to decode</param>
            /// <returns>The polyline as List&lt;GeoPoint&gt;</returns>
            public static List<GeoPoint> DecodeCoord(string encoded) {
                List<GeoPoint> locs = new List<GeoPoint>();
                GeoPoint next;
                int index = 0;
                double lat = 0.0;
                double lng = 0.0;

                lat += decodePoint(encoded, index, out index);
                lng += decodePoint(encoded, index, out index);
                locs.Add(new GeoPoint((lat * 1e-5), (lng * 1e-5)));

                while (index < encoded.Length) {
                    lat += decodePoint(encoded, index, out index);
                    lng += decodePoint(encoded, index, out index);
                    next = new GeoPoint((lat * 1e-5), (lng * 1e-5));
                    if (next != locs.Last()) {
                        locs.Add(next);
                    }
                }
                return locs;
            }

            /// <summary>
            /// Decodes a single number from an encoded string and
            /// return it as integer number
            /// </summary>
            /// <param name="encoded">The string where the number is in</param>
            /// <param name="startIndex">The index of the first char of the number's encoded form</param>
            /// <param name="finishIndex">The new value of the index, updated after the decoding process</param>
            /// <returns>The decoded number as integer</returns>
            private static int decodePoint(string encoded, int startIndex, out int finishIndex) {
                int binaryNum;
                int shift = 0;
                int result = 0;

                do {
                    binaryNum = Convert.ToInt32(encoded[startIndex++]) - 63;
                    result |= (binaryNum & 0x1f) << shift;
                    shift += 5;
                } while (binaryNum >= 0x20);

                int decodedP = (((result & 1) > 0) ? ~(result >>  1) : (result >>1));

                finishIndex = startIndex;
                return decodedP;
            }

        } 
        #endregion

        #region GeoTrip.GPolylineDescriptor

        /// <summary>
        /// Groups field necessary to compose a GPolyline
        /// object at the same way of 
        /// <seealso href="http://code.google.com/apis/maps/documentation/reference.html">
        /// Google Maps Api</seealso>
        /// Descriptor for the GPolyline google object.
        /// </summary>
        [DataContract]
        public struct GPolylineDescriptor
        {
            /// <summary>
            /// Encoded polyline points.
            /// </summary>
            [DataMember]
            public string points;

            /// <summary>
            ///String containing the encoded polyline zoom
            ///level groups
            /// Polyline levels.
            /// </summary>
            [DataMember]
            public string levels;

            /// <summary>
            ///Number of zoom levels contained in the encoded
            /// numLevels field.
            /// </summary>
            [DataMember]
            public int numLevels;

            /// <summary>
            /// zoomFactor field.
            /// </summary>
            [DataMember]
            public int zoomFactor;

        }

        #endregion

    }
}
